package com.dyz.leetcode;

import java.util.Arrays;

public class LengthOfLIS300 {
    //动态规划
    public int lengthOfLIS(int[] nums) {
        if(nums==null|| nums.length==0){return 0;}
        if(nums.length==1){return 1;}
        int[] dp = new int[nums.length];
        //base case
        Arrays.fill(dp, 1);
        int res = 1;
        for(int i=0; i<nums.length; i++){
            for(int j=0; j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
            res = Math.max(dp[i], res);
        }
        return res;
    }
}
